Let H be a Hilbert space ( inner product space that is complete with respect to the norm induced by the inner product) and M be a finite dimensioal subspace of H. Then for any x∈H, there exists a unique y∈M such that
m∈Mmin∥x−m∥
has a unique solution y. In other words "we can find a unique point in M that is closest to x". If m∗ is the closest point to x in M, then x−m∗⊥M.
Proof: See lecture notes.
Remark: The proof stated that m∗=x1 is the closest point to M. It can also be interpreted as the best approximation of x choosen from the vectors in M. The x2 term is the error in the approximation.
Example: Let V=R2 and M=span{[1,1]T}. Find the best approximation of x=[4,7]T in M.
Solution: We need to find m∗ such that m∗=α[11] and ∥x−m∗∥ is minimum.
(x−m∗)⊥M⟹<x−m∗,m>=0∀m∈M<x−m∗,[11]>=0Replace x and m∗ with their values.<[4−α7−α],[11]>=0Recall that <x,y>=xTy.4−α+7−α=0α=211m∗=211[11]
Example: Let x∈V and M=span{v1,v2}. Find the best approximation of x in M.
Solution: We need to find m∗ such that m∗=α1v1+α2v2 that is in the span of M and ∥x−m∗∥ is minimum.
(x−m∗)⊥M⟹(x−m∗)⊥both v1 and v2<x−α1v1−α2v2,v1>=<x,v1>−α1<v1,v1>−α2<v2,v1>=0<x−α1v1−α2v2,v2>=<x,v2>−α1<v1,v2>−α2<v2,v2>=0[<v1,v1><v1,v2><v2,v1><v2,v2>][α1α2]=[<x,v1><x,v2>][α1α2]=[<v1,v1><v1,v2><v2,v1><v2,v2>]−1[<x,v1><x,v2>]m∗=α1v1+α2v2
Example: Let V=R3 and M=span{[1,1,1]T,[1,0,1]T}. Find the best approximation of x=[4,7,2]T in M.
Solution: We need to find m∗ such that m∗=α1⎣⎡111⎦⎤+α2⎣⎡101⎦⎤ that is in the span of M and ∥x−m∗∥ is minimum.
(x−m∗)⊥M⟹(x−m∗)⊥both v1 and v2[<v1,v1><v1,v2><v2,v1><v2,v2>][α1α2]=[<x,v1><x,v2>]Recall that <x,y>=xTy.[3222][α1α2]=[136][α1α2]=[3222]−1[136][α1α2]=[1−1−13/2][136][α1α2]=[7−4]m∗=α1v1+α2v2=7⎣⎡111⎦⎤−4⎣⎡101⎦⎤=⎣⎡373⎦⎤
Example: Let H be the space of square integrable functions on [−π,π] with inner product <f,g>=∫−ππf(t)g(t)ˉdt. Let M be the subspace of H, M=span{ejkt/2π}, k from −N to N. Note that dimension of M is 2N+1.
<fn,fm>=∫−ππ2πejnt2πe−jmtdt=2π1∫−ππej(n−m)tdtIf n=m, then 2π1∫−ππej(n−m)tdt=2π1j(n−m)ej(n−m)t∣∣−ππ=0If n=m, then 2π1∫−ππej(n−m)tdt=2π1∫−ππ1dt=1Therefore, <fn,fm>={10if n=mif n=m
Now, let g∈H be an arbitrary function. Then g=g1+g2 where g1∈M and g2∈M⊥. We need to find g1 such that ∥g−g1∥ is minimum.
g1=k=−N∑Nαk2πejkt where αk=<g,fk>=∫−ππg(t)2πe−jktdtαk=∫−ππg(t)2πe−jktdtg1=k=−N∑N∫−ππg(t)2πe−jkt2πejktdt=k=−N∑N∫−ππg(t)2π1dt=∫−ππg(t)dt
Example: Find the orthagonal projection of the vector ⎣⎡100⎦⎤ onto the subspace M=span{⎣⎡111⎦⎤,⎣⎡1−11⎦⎤}.
Solution: We know that the projection matrix is P=B(BTB)−1BT where B is the matrix whose columns are the basis vectors of M. Therefore,
Example: Let A=⎣⎡22221111⎦⎤ and b=⎣⎡l1l2l3l4⎦⎤. Find x such that Ax=b.
Solution: Now, the rows of A are linearly dependent. Therefore, A is not full column rank. Therefore, there is no exact solution. We need to find the best approximation of b in range(A).
b∗=⎣⎡lˉlˉlˉlˉ⎦⎤ where lˉ=4l1+l2+l3+l4⎣⎡22221111⎦⎤[x1x2]=⎣⎡lˉlˉlˉlˉ⎦⎤[x1x2]=[lˉ−lˉ] is any solution, more examples [1−1],[2−3],[3−5],…A minimum norm solution is can be found by minimizing the norm of x. For that, we can project any solution onto the null space perpendicular to A.x1=ProjN(A)⊥[lˉ−lˉ]Corollary: N(A)⊥=range(A∗)A∗=[21212121]range(A∗)=span{[21]}ProjN(A)⊥[lˉ−lˉ]=Projrange(A∗)[lˉ−lˉ]Projrange(A∗)[lˉ−lˉ]=<[21],[21]><[lˉ−lˉ],[21]>[21]Projrange(A∗)[lˉ−lˉ]=5lˉ[21] Or in projection matrix form, Q=[21] then, P=Q(Q∗Q)−1Q∗P=[21]51[21]=[4/52/52/51/5]x1=Px=[4/52/52/51/5][lˉ−lˉ]=[4/5lˉ−2/5lˉ2/5lˉ−1/5lˉ]=[2/5lˉ1/5lˉ]=lˉ/5[21]
Special Cases of Ax=b
1.1 Columns of A are linearly independent
If the columns of A are linearly independent, then A is full rank and ATA is invertible. Therefore, x=(ATA)−1ATb is the unique solution.
A is full column rank with A is m×n and m≥n if and only if N(A)={0}. (Tall matrix)
If b∈range(A), then the solution exists and is unique. If b∈/R(A), then the solution does not exist.
Ax=ProjR(A)b is the best approximation of b in R(A).
P=A(ATA)−1AT is the projection matrix onto R(A).
Ax=A(ATA)−1ATb is the best approximation of b in R(A).
Ax−A(ATA)−1ATb=0 since the projection of b onto R(A).
A(x−(ATA)−1ATb)=0
x−(ATA)−1ATb∈N(A) and the null space contains only the zero vector.
x=(ATA)−1ATb is the unique solution.
1.2 Columns of A are linearly dependent
If the columns of A are linearly dependent, then A is not full rank and ATA is not invertible. Therefore, x=(ATA)−1ATb is not the unique solution.
2.1 Rows of A are linearly independent
If the rows of A are linearly independent, then A is full row rank and AAT is invertible. Therefore, x=AT(AAT)−1b is the unique solution.
A is full row rank with A is m×n and m≤n if and only if N(AT)={0}. (Wide matrix)
If b∈range(A), then the solution exists and is unique. If b∈/R(A), then the solution does not exist.
dim(R(A))=dim(R(AT))=rank(A)=rank(AT)⟹b∈R(A)
For a minimum norm solution, we need to project b onto the null space perpendicular to A.
x=ProjN(A)⊥b=ProjR(A∗)b
P=A∗(AA∗)−1A=A∗(A∗A)−1A
Px=A∗(AA∗)−1Ax=A∗(AA∗)−1b
2.2 Rows of A are linearly dependent
If the rows of A are linearly dependent, then A is not full row rank and AAT is not invertible. Therefore, x=AT(AAT)−1b is not the unique solution.
3.1 A is square and invertible
If A is square and invertible, then x=A−1b is the unique solution.
Example: Let A=⎣⎡113122131⎦⎤ and b=⎣⎡12−1⎦⎤. Find x such that Ax=b.
Solution:
First, we need to check if b∈range(A). Since A has linearly dependent columns
Now, the problem has a solution.
However for the uniqueness, we need to check if A is full row rank. Since A has linearly dependent rows, A is not full row rank. Therefore, the solution is not unique, hence we need to find the minimum norm solution. For that, we need to project b onto the null space perpendicular to A.
Starting with any solution x,
x=⎣⎡x1x2x3⎦⎤Let x1=0⎣⎡113122131⎦⎤⎣⎡0x2x3⎦⎤=⎣⎡1/313/6−5/6⎦⎤x2=6−7 and x3=69x=⎣⎡0−7/69/6⎦⎤Now, xmin is the projection of x onto the null space perpendicular to A.xmin=ProjN(A)⊥x=ProjR(A∗)xA∗=⎣⎡111123321⎦⎤range(A∗)=span{⎣⎡111⎦⎤,⎣⎡123⎦⎤}Q=⎣⎡111123⎦⎤P=Q(Q∗Q)−1Q∗P=⎣⎡111123⎦⎤[36614]−1[111213]P=61⎣⎡52−1222−125⎦⎤xmin=Px=61⎣⎡52−1222−125⎦⎤⎣⎡0−7/69/6⎦⎤=⎣⎡−25/364/3631/36⎦⎤